#include "linearList.h"
using namespace std;

//初始化顺序表
sequenceList::sequenceList(const int& capacity,const int& initLength,float initArray[])
{
    maxCapcity=capacity;

    myList=new float[maxCapcity];

    curNumberOfItem=(initLength<=maxCapcity)?initLength:maxCapcity;

    for(int i=0;i<curNumberOfItem;i++){

        myList[i]=initArray[i];
        
    }
}
//销毁顺序表
sequenceList::~sequenceList(){

    if(myList!=nullptr){
        delete[] myList;
        myList=nullptr;
    }
}
//添加元素
bool sequenceList::addItem(const float& item){
    if(curNumberOfItem>=maxCapcity){
        return false;
    }
    myList[curNumberOfItem]=item;
    curNumberOfItem++;

    return true;
}
//插入元素
bool sequenceList::insertItem(const int& index,const float&item){
    if(index<0||index>curNumberOfItem){
        return false;
    }
    if(curNumberOfItem>=maxCapcity){
        return false;
    }
    for(int i=curNumberOfItem;i>index;i--){
        myList[i]=myList[i-1];
    }
    myList[index]=item;
    curNumberOfItem++;
    return true;
}
//删除元素
int sequenceList::deleteItem(const float& item){
    for(int i=0;i<curNumberOfItem;i++){
        if(myList[i]==item){
            for(int j=i;j<curNumberOfItem-1;j++){
                myList[j]=myList[j+1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

//查找元素
bool sequenceList::locate(const int& index,float& val){
    if(index<0||index>=curNumberOfItem){
        return false;
    }
    val=myList[index];
    return true;
}

//查找元素（按值）
int sequenceList::locate(const float& item){
    for(int i=0;i<curNumberOfItem;i++){
        if(myList[i]==item){
            return i;
        }
    }
    return -1;
}
//倒序排列元素
void sequenceList::reverse(){
    if(curNumberOfItem<2){
        return;
    }
    int a=0;
    int b=curNumberOfItem-1;
    while(a<b){
        float temp=myList[a];
        myList[a]=myList[b];
        myList[b]=temp;
        a++;
        b--;
    }

}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

// listNode 构造函数
listNode::listNode(float nodeData, listNode* succ)
{
    data=nodeData;
    next=succ;
}
// listNode 析构函数
listNode::~listNode()
{
    // 这里可以留空，因为 listNode 没有动态分配的资源
    // 如果 next 指向需要手动释放的资源，应该在这里处理
    // 但在这个实现中，linkList 类负责管理所有节点的生命周期
}
// 初始化链表
linkList::linkList(const int& length, float initArray[])
{
    firstNode = new listNode(); 
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;

    for (int i = 0; i < length; i++)
    {
        listNode* newNode = new listNode(initArray[i]);
        lastNode->next = newNode;
        lastNode = newNode;
        listSize++;
    }
}
// 销毁链表
linkList::~linkList()
{
    listNode* current = firstNode;
    while(current != nullptr) {
        listNode* nextNode = current->next;  
        delete current;                      
        current = nextNode;                  
    }
    firstNode = nullptr;
    curNode = nullptr;
    lastNode = nullptr;
    listSize = 0;
}

//头插法
bool linkList::headInsertItem(const float& item){
    listNode* newNode=new listNode(item,firstNode->next);
    if(firstNode==lastNode){ //防止尾指针不发生变化
        lastNode=newNode;
    }
    firstNode->next=newNode;
    listSize++;
    return true;
}

//尾插法
bool linkList::tailInsertItem(const float& item){
    listNode* newNode=new listNode(item);
    if(firstNode==lastNode){
        firstNode->next=newNode;
    }else{
        lastNode->next=newNode;
    }
    lastNode=newNode;
    listSize++;
    return true;
}

//插入元素
int linkList::insertItem(const int& index,const float& item){
    if(index<0||index>listSize){
        return -1;
    }
    if(index==0){
        return headInsertItem(item)?0:-1;
    }
    if(index==listSize){
        return tailInsertItem(item)?index:-1;
    }
    listNode* pre=firstNode;
    for(int i=0;i<index;i++){
        pre=pre->next;
    }
    listNode* newNode=new listNode(item,pre->next);
    pre->next=newNode;
    listSize++;
    return index;
}

//删除元素
int linkList::deleteItem(const float& item){
    if(firstNode==lastNode){
        return -1;
    }
    listNode* prev=firstNode;
    listNode* curr=firstNode->next;
    int index=0;
    while(curr!=nullptr){
        if(curr->data==item){
            prev->next=curr->next;
            if(curr==lastNode){
                lastNode=prev;
            }
            delete curr;
            listSize--;
            return index;
        }
        prev=curr;
        curr=curr->next;
        index++;
    }
    return -1;
}

//查找元素（按序号）
bool linkList::locate(const int& index,float& val){
    if(index<0||index>=listSize){
        return false;
    }
    listNode* curr=firstNode->next;
    for(int i=0;i<index;i++){
        curr=curr->next;
    }
    val=curr->data;
    return true;
}

//查找元素（按值查找）
int linkList::locate(const float& item){
    if(firstNode==lastNode){
        return -1;
    }
    listNode* curr=firstNode->next;
    int index=0;
    while(curr!=nullptr){
        if(curr->data==item){
            return index;
        }
        curr=curr->next;
        index++;
    }
    return -1;
}

//递增排序
// 对链表进行递增排序
void linkList::ascendingOrder()
{
    // 如果链表为空或只有一个元素，直接返回
    if (listSize <= 1) {
        return;
    }
    
    // 使用冒泡排序算法对链表进行排序
    bool swapped;
    do {
        swapped = false;
        listNode* prev = firstNode;
        listNode* current = firstNode->next;
        
        while (current != nullptr && current->next != nullptr) {
            listNode* nextNode = current->next;
            
            // 如果当前节点值大于下一个节点值，交换它们
            if (current->data > nextNode->data) {
                // 交换节点数据
                float temp = current->data;
                current->data = nextNode->data;
                nextNode->data = temp;
                swapped = true;
            }
            
            // 移动到下一个节点
            prev = current;
            current = current->next;
        }
    } while (swapped);  // 如果本轮有交换，继续排序
}

// 倒序排列链表元素
void linkList::reverse()
{
    // 如果链表为空或只有一个元素，直接返回
    if (listSize <= 1) {
        return;
    }
    
    // 使用三指针法反转链表
    listNode* prev = nullptr;          // 前一个节点
    listNode* current = firstNode->next; // 当前节点（第一个数据节点）
    listNode* next = nullptr;          // 下一个节点
    
    // 记录原来的第一个数据节点，反转后将变成最后一个节点
    listNode* originalFirst = firstNode->next;
    
    // 遍历链表，反转每个节点的指向
    while (current != nullptr) {
        // 保存下一个节点
        next = current->next;
        
        // 反转当前节点的指向
        current->next = prev;
        
        // 移动指针
        prev = current;
        current = next;
    }
    
    // 更新头节点的next指向新的第一个节点
    firstNode->next = prev;
    
    // 更新尾指针指向原来的第一个节点（现在是最后一个节点）
    lastNode = originalFirst;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

void merge(linkList& A, linkList& B)
{
    if (B.getFirstNode() == B.getLastNode()) {
        return;
    }
    
    if (A.getFirstNode() == A.getLastNode()) {
        B.reverse();
        A.getFirstNode()->next = B.getFirstNode()->next;
        A.setLastNode(B.getLastNode());
        A.setListSize(B.getListSize());
        
        B.getFirstNode()->next = nullptr;
        B.setLastNode(B.getFirstNode());
        B.setListSize(0);
        return;
    }
    
    A.ascendingOrder();
    B.ascendingOrder();
    
    listNode* tempHead = new listNode();
    listNode* tail = tempHead;
    
    listNode* pA = A.getFirstNode()->next;
    listNode* pB = B.getFirstNode()->next;
    
    while (pA != nullptr && pB != nullptr) {
        if (pA->data <= pB->data) {
            tail->next = pA;
            pA = pA->next;
        } else {
            tail->next = pB;
            pB = pB->next;
        }
        tail = tail->next;
    }
    
    if (pA != nullptr) {
        tail->next = pA;
    } else {
        tail->next = pB;
    }
    
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    
    listNode* prev = nullptr;
    listNode* current = tempHead->next;
    listNode* next = nullptr;
    
    listNode* originalFirst = tempHead->next;
    
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    A.getFirstNode()->next = prev;
    A.setLastNode(originalFirst);
    A.setListSize(A.getListSize() + B.getListSize());
    
    B.getFirstNode()->next = nullptr;
    B.setLastNode(B.getFirstNode());
    B.setListSize(0);
    
    delete tempHead;
}